package cxydmmszl.chapter08.t125.b1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.HashMap;

/**
 * <li style="color: red;">Prob</li>
 * 未排序数组中累加和为给定值的最长子数组系列问题补1
 * <li style="color: green;">Desc</li>
 * 给定一个无序数组arr，其中元素可正、可负、可 0。
 * 求 arr 所有子数组中正数与负数个数相等的最长子数组的长度。
 * <br/><br/>[要求]<br/>
 * 时间复杂度为 O(n)，空间复杂度为 O(n)
 * <br/><br/>备注：<br/>
 * &emsp;1⩽N⩽10^5<br/>
 * &emsp;-100⩽arr[i]⩽100<br/>
 * <li style="color: green;">Input</li>
 * 第一行一个整数N，表示数组长度
 * 接下来一行有N个数表示数组中的数
 * <li style="color: green;">Output</li>
 * 输出一个整数表示答案
 * <li style="color: blue;">Link</li> CD10
 *
 * @author habitplus
 * @since 2021-10-08 10:39
 */
public class Main {
    static StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) st.nval;
    }

    public static void main(String[] args) {
        int n = nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
        }

        // 思路：只需要将数组中的正数改为 1，负数改为 -1，0 不变，
        // 即原问题可以改为【求累加和为 0 的最长子数组的长度】
        for (int i = 0; i < n; i++) {
            if (arr[i] > 0) {
                arr[i] = 1;
            } else if (arr[i] < 0){
                arr[i] = -1;
            }
        }
        int ans = maxLength(arr, 0);
        System.out.println(ans);
    }

    private static int maxLength(int[] arr, int k) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int n = arr.length;
        // 表示从位置 0 开始累加的和
        int sum = 0;
        // key 表示累加的和，value 表示最早出现该累加和的位置下标
        HashMap<Integer, Integer> map = new HashMap<>();
        // 代表子数组的和为 k 的最大长度
        int res = 0;
        // 表示什么都没加的时候，位置为 -1；
        map.put(0, -1);

        for (int i = 0; i < n; i++) {
            sum += arr[i];
            if (map.containsKey(sum - k)) {
                res = Math.max(res, i - map.get(sum - k));
            }

            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
        }
        return res;
    }
}
